//题目:
// 按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
// n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
// 给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
// 每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
#include<iostream>
#include<vector>

using namespace std;
//代码:
class Solution 
{   
    vector<string> v;
    vector<vector<string>> ret;

    bool row[9]={0},col[9]={0};//标记某点坐标的状态
    vector<pair<int,int>> v_arr;
public:
    bool is_valid(int x,int y,int n)
    {
        for(const pair<int,int>& pir:v_arr)
        {
            //判断(x,y)斜交叉路径上是否有皇后即可
            for(int i=1;i<n;i++)
            {
                //左斜向上
                if(x-i>=0 && y-i>=0 && x-i==pir.first && y-i==pir.second)return false;
                //右斜向下
                if(x+i<n && y+i<n && x+i==pir.first && y+i==pir.second)return false;
                //左斜向下
                if(x+i<n && y-i>=0 && x+i==pir.first && y-i==pir.second)return false;
                //右斜向上
                if(x-i>=0 && y+i<n && x-i==pir.first && y+i==pir.second)return false;
            }
        }
        return true;
    }
    void dfs(int n,int level,string str)
    {
        if(level==n){
            ret.push_back(v);
            return;
        }
        //每层有n的位置，选取不同的位置，并标记
        for(int i=0;i<n;i++)
        {
            if(row[level]==false && col[i]==false && is_valid(level,i,n))
            {
                str[i]='Q';//第level行，第i个元素放置N皇后
                v.push_back(str);
                row[level]=true,col[i]=true,v_arr.push_back(make_pair(level,i));
                dfs(n,level+1,string(n,'.'));
                //回溯
                str[i]='.',v.pop_back();//
                row[level]=false,col[i]=false,v_arr.pop_back();//标识回溯
            }
        }
    }
    vector<vector<string>> solveNQueens(int n) 
    {
        //从第0层开始，一共n层
        dfs(n,0,string(n,'.'));

        return ret;
    }
};